Bluetooth (BT) is a relatively new specification for wireless communication of data and voice based on a low-cost short-range radio link. It can be built into a 9×9 mm microchip, what facilitates ad hoc connections for both stationary and mobile communication environments. Information in this application is in part based on the Bluetooth specification, “Specification of the Bluetooth System”, Jul. 26, 1999, the entirety of which is hereby incorporated by reference.
The original intention in making the specification of Bluetooth was to eliminate cables between telephones, PC-cards (Personal Computer cards), wireless headsets, etc., but today the Bluetooth specification is used for establishing true ad hoc wireless networks intended for both synchronous traffic, e.g. voice, and asynchronous traffic, e.g. data traffic based on the IP (the Internet Protocol). Now the intention of the Bluetooth specification comprises that any commodity device such as telephones, personal digital assistants (PDAs), laptop computers, digital cameras video monitors, printers, fax machines, etc. should be capable of communicating over a radio interface, i.e. any of these devices could contain a radio chip made according to the Bluetooth specification and having the software specified therefor.
In addition to merely replacing the cables between various devices, the use of the Bluetooth specification in various device provides a bridge to existing data networks and their peripheral devices, and a mechanism to form small private ad hoc groupings for connected devices away from fixed network structures or connected to a fixed network structure via a gateway. According to the Bluetooth specification the wireless communication uses a fast acknowledgement and frequency hopping scheme to make the radio links between devices adapted to communicate according to the Bluetooth specification robust. The devices avoid interference with one another by hopping to a new frequency or channel after transmitting or receiving a packet. Compared to other systems operating in the same frequency band, in the wireless communication according to the Bluetooth specification typically frequency hops are made faster and shorter packets are used. The radio band used by devices adapted to communicate according to the Bluetooth specification is the unlicensed 2.4 GHz Industrial-Scientific-Medical (ISM) band with a channel spacing of 1 MHz.
A device adapted to communicate according to the Bluetooth specification includes a radio unit, a link control unit and a support unit for link management and host terminal interface function. According to the specification a point-to-point connection can be provided in the case, where only two units adapted to communicate according to the Bluetooth specification are involved, or a point-to-multipoint connection in the case of more than two units. For a point-to-multipoint connection, the radio band is shared by several units adapted to communicate according to the Bluetooth specification. Two or more units adapted to communicate according to the Bluetooth specification form a small network called a piconet, see FIGS. 1a-1c. Within a piconet, a unit adapted to communicate according to the Bluetooth specification can have either of two roles: it can be a master or a slave. Within each piconet there may be only oral master and one slave, see FIG. 1a, or more than one up to seven active slaves, see FIG. 1b. Any unit adapted to communicate according to the Bluetooth specification can become a master in a piconet.
Furthermore, two or more piconets can be interconnected, form a composite network called a scatternet, see FIG. 1c. The connection point between two piconets consists of a unit C adapted to communicate according to the Bluetooth specification that is a member of both piconets. A unit adapted to communicate according to the Bluetooth specification can simultaneously be a slave member of multiple piconets, but only a master in one piconet, and thus a unit adapted to communicate according to the Bluetooth specification and acting as a master in one piconet can participate in other piconets only as a slave. A unit adapted to communicate according to the Bluetooth specification can only transmit and receive data in one piconet at a time, and therefore participation in multiple piconets is made on a time division multiplex basis.
The Bluetooth specification provides full-duplex transmission built on slotted Time Division Duplex (TDD), where each slot is 0.625 ms long. The time slots are numbered sequentially using a large number range, which is cyclic with a cycle length of 227. Master-to-slave transmission always starts in an even-numbered time slot while slave-to-master transmission always starts in an odd-numbered time slot. The combination of an even-numbered time slot and its subsequent odd-numbered time slot is called a frame, the frame thus including a master-to-slave time slot and a slave-to-master time slot, except in the case where multi-slot packets are used and longer frames are used. There is no direct transmission between slaves, neither within a piconet or between two different piconets.
The communication within a piconet is organised such that the master polls each slave according to some polling schedule. With one exception, a slave is only allowed to transmit after having been polled by the master. The slave will then start its transmission in the slave-to-master time slot immediately following the packet received from the master. The master may or may not include data in the packet used to poll a slave. The only exception to the above principle is that when a slave is connected by an established Synchronous Connection Oriented (SCO) link it is always allowed to transmit in the pre-allocated slave-to-master time slot, even if not explicitly polled by the master in the preceding master-to-slave time slot.
Each unit adapted to communicate according to the Bluetooth specification has a globally unique 48-bit IEEE 802 address. This address, called the Bluetooth unit Address (BD_ADDR), is assigned at the time when the unit is manufactured and it is never changed. In addition thereto the master of a piconet assigns a local Active Member Address (AM_ADDR) to each active slave member of the piconet. The AM_ADDR, which is only three bits long, is dynamically assigned and de-assigned and is unique only within a single piconet. The master uses the AM_ADDR when polling a slave in a piconet. However, when the slave, triggered by a packet from the master addressed using the AM_ADDR of the slave, transmits a packet to the master, it includes its own AM_ADDR and not the AM_ADDR of the master in the packet header since an AM_ADDR of the master does not exist. Thus, the master of a piconet never assigns an AM_ADDR to itself.
Although all data are transmitted in packets, the packets can carry both synchronous data, on the mentioned Synchronous Connection Oriented links, mainly intended for voice traffic, and asynchronous data, on Asynchronous ConnectionLess (ACL) links. An SCO link is a symmetric point-to-point link between the master and a specific slave. The SCO link reserves slots and can therefore be considered as a circuit-switched connection between the master and the slave. An ACL link is a point-to-multipoint link between the master and all the slaves participating in the piconet. Slots may be reserved for SCO links, as indicated above, and in slots not reserved for such links the master can establish an ACL link on a per slot basis to any slave. The ACL link provides a packet-switched connection between the master and all active slaves participating in the piconet.
Depending on the type of packet used, an acknowledgement and retransmission scheme is used to ensure reliable transfer of data, such a scheme not being used for packets on SCO links transferring synchronous data. Forward error correction (FEC) in the form of channel coding is also used which limits the impact of random noise on long-distance links.
The standard format of a packet used for transmission according to the Bluetooth specification is illustrated in FIG. 2, this format not being used for some types of control packets. A standard packet has a field for an access code having the length of 72 bits and a header field of a length of 54 bits. There is a field for the payload which has a length that can range from zero to a maximum of 2745 bits. The AM_ADDR is located in the packet header followed by some control parameters, e.g. a bit indicating acknowledgement or retransmission request of the previous packet, when applicable, and a header error check (HEC).
The access code used in a packet can be one of three different types: Channel Access Code (CAC), Device Access Code (DAC), and Inquiry Access Code (IAC):                The Channel Access Code identifies a channel that is used in a certain piconet, i.e. essentially the CAC identifies the piconet. All packets exchanged within a piconet carry the same the CAC. The CAC is derived from the BD_ADDR of the master unit of the piconet.        The Device Access Code is derived from a BD_ADDR of a particular unit adapted to communicate according to the Bluetooth specification. It is used for special signalling procedures, e.g. the PAGE procedure.        The Inquiry Access Code appears in two variants: the General Inquiry Access Code (GIAC) and the Dedicated Inquiry Access Code (DIAC). Both are used in the INQUIRY procedure, that will be explained in more detail below.        
The format of the payload depends on the type of packet. The payload of an ACL packet consists of a header, a data field and, with the exception of AUX1 type packets, a cyclic redundancy check (CRC). The payload of a Synchronous Connection Oriented (SCO) packet consists of a single data field. In addition, there are hybrid packets including two data fields, one for synchronous data and one for asynchronous data. Packers in which the payload does not include a CRC are neither acknowledged nor retransmitted.
The protocol layers of a network formed by units adapted to communicate according to the Bluetooth specification are illustrated in FIG. 3. The Baseband, LMP and L2CAP represent existing Bluetooth specific protocols. The “High level protocol or application” layer represents protocols that may or may not be Bluetooth specific while the Network layer is not defined in the Bluetooth specification.
A limitation of the Bluetooth specification is that therein no method is explicitly provided to address and route packets from one piconet to another. Thus, inter-piconet communication performed in a scatternet is not specified, although there are proposals for how to achieve this.
An important capability in any ad hoc networking method is the neighbour discovery feature. Such a feature is also defined in the Bluetooth specification. Without a neighbour discovery capability, a unit adapted to communicate according to the Bluetooth specification would not be capable of finding any other units adapted to communicate according to the Bluetooth specification with which it could communicate and consequently no ad hoc network could be formed. The neighbour discovery procedure according to the Bluetooth specification consists of the INQUIRY message and the INQUIRY RESPONSE message. An “inquiry” procedure is defined which is used in applications where the device address of the destination is unknown to the source. For example, public facilities like printers or facsimile machines can be considered. Alternatively, the inquiry procedure can be used to discover other units adapted to communicate according to the Bluetooth specification which are located within the range of the transceiver of a considered unit adapted to communicate according to the Bluetooth specification.
A unit adapted to communicate according to the Bluetooth specification and wanting to discover neighbouring units also adapted to communicate according to the Bluetooth specification, neighbouring meaning within radio coverage of the first unit, will repeatedly transmit according to well specified timing and frequency sequences, INQUIRY messages and listen for INQUIRY RESPONSE messages, which are optional. An INQUIRY message consists of only an Inquiry Access Code (IAC). It does not contain any information about the source but may indicate the class of devices which should respond. The Inquiry Access Code can be a General Inquiry Access Code (GIAC), which is sent to discover any unit adapted to communicate according to the Bluetooth specification in the neighbourhood, or a Dedicated Inquiry Access Code (DIAC), which is sent to discover only a certain type of units adapted to communicate according to the Bluetooth specification, for which a particular DIAC is dedicated.
A unit adapted to communicate according to the Bluetooth specification receiving an INQUIRY message, including a GIAC or an appropriate DIAC, may respond by sending an INQUIRY RESPONSE message. The INQUIRY RESPONSE message is actually an Frequency Hop Synchronisation (FHS) packet, see FIG. 4. The FHS packet is a special control packet revealing, among other things, the transmitting unit and the clock of the transmitting unit. The payload field in such a packet includes eleven fields. All fields in the packet, except the AM_ADDR field, and of course the “Undefined” field, indicate properties or parameters of the unit that sends the FHS packet. The Lower Address Part (LAP), Upper Address Part (UAP) and Non-significant Address Part (NAP) fields together form the BD_ADDR. The “class of device” field indicates the class of device of the unit. The CLK field contains the current value of the internal clock of the unit. The SR, SP and “Page scan mode” fields all contain control parameters concerning the PAGE procedure. The contents of the AM_ADDR field can be used to assign an AM_ADDR to a unit which will become a slave in a piconet, and otherwise these three bits should all be set to zero. The “Undefined” field is reserved for future use and includes two bits, which should be set to zero. By listening for INQUIRY RESPONSE messages the unit that initiated the INQUIRY procedure can collect the BD_ADDR and internal clock values of the neighbouring units also adapted to communicate according to the Bluetooth specification.
An FHS packet is also used for other purposes according to the Bluetooth specification, in addition to the use as the INQUIRY RESPONSE message, e.g. for synchronising the frequency hop channel sequence, a paged master response and in the master-slave switch.
Related to the INQUIRY procedure is the PAGE procedure, which is used to establish an actual connection between two units adapted to communicate according to the Bluetooth specification. Once the BD_ADDR of a neighbouring unit is known to a unit, the paging unit, as a result of an INQUIRY procedure, the neighbouring unit can be paged by sending a PAGE message. Also the knowledge of the internal clock value of the unit to be paged will potentially speed up the PAGE procedure, since it makes it possible for the paging unit to estimate when and on which frequency hop channel the neighbouring unit will listen for PAGE messages.
A PAGE message consists of the Device Access Code (DAC), derived from the BD_ADDR of the paged unit. A unit adapted to communicate according to the Bluetooth specification and receiving a PAGE message including its own DAC responds by sending an identical packet, i.e. including only the DAC of the paged unit. The paging unit then replies by sending an FHS packet, including the BD_ADDR of the paging unit, the current value of the internal clock of the paging unit, the AM_ADDR assigned to the paged unit and some other parameters, see FIG. 4. The paged unit then responds once again by transmitting its DAC and thereby the connection between the two units is established.
If the paging unit already was the master of a piconet, the paged unit has now joined this piconet as a new slave unit. Otherwise, the two units have just formed a new piconet having the paging unit as the master unit. Since the INQUIRY message does not include any information on the sender thereof, in particular not its BD_ADDR, the unit that initiated the INQUIRY procedure is the only unit that can initiate a subsequent PAGE procedure. Thus, the unit initiating an INQUIRY procedure will also be the master of any new piconet that is formed as a result of a subsequent PAGE procedure. If considered necessary, however, the roles of master and slave can be switched using the master-slave-switch mechanism defined in the Bluetooth specification. This is a complex and extensive procedure resulting in a redefinition of the entire piconet, involving all other slave units in the piconet.
The INQUIRY and PAGE procedures are well specified in the Bluetooth specification. They are the only tools that are needed to form a new piconet or to join an existing one. Although the tools as such are well specified, there are no rules or guidelines as to how to use them. When neighbours are discovered there is no way of knowing to which thereof a connection should be made to in order to form an appropriate piconet. Even if the master-slave-switch mechanism exists, using it is an extensive procedure and it is difficult to know when to use it in order to improve the efficiency of piconet. Hence, piconets will be more or less established at random, often resulting in far from optimal piconet and scatternet structures.
An exception exists in the case where the unit wanting to establish a connection already knows the BD_ADDR of the unit to which it wants to connect. The use of the Dedicated Inquiry Access Code in the INQUIRY messages and the class of device field in the FHS packet, indicating the class of device of the unit that sends the FHS packet, can also be used to impose a certain control of the establishment of piconets. Nevertheless, units adapted to communicate according to the Bluetooth specification and forming a piconet or a scatternet generally result in less than optimal networks being formed.
The information exchanged during the INQUIRY and PAGE procedures is not sufficient to determine how to establish connections in order to form an efficient piconet. Furthermore, the fact that the unit that initiates an INQUIRY procedure will have to be the master of any new piconet that is formed as a result of a subsequent PAGE procedure makes the forming of piconets and scatternets inflexible. The complex and extensive master-slave-switch mechanism is too inefficient to compensate for this inflexibility.
Consider, for instance, a scenario in which a number of people have gathered in a conference room for a meeting. They turn on their laptops, which have circuits to communicate according to the Bluetooth specification and at random start to send INQUIRY messages and listen for INQUIRY messages from other units. Some other people may also later join the meeting resulting in more INQUIRY procedures. The result of these random INQUIRY procedures, followed by PAGE procedures and the forming of piconets, may well be something like the interconnected networks shown in FIG. 5, whereas an optimal piconet structure could be similar to the network shown in FIG. 6.
When a new unit moves into the neighbourhood of an existing piconet, e.g. as could be the case in this meeting scenario, it may want to communicate with the units connected to that piconet. The unit would then obviously like to join the piconet as a new slave unit. However, the means by which to achieve this as provided by the Bluetooth specification are few and inefficient. The unit would have to wait and hope to be discovered by the master unit of the piconet, by receiving an INQUIRY message from the master unit, and to be subsequently paged and connected. However, when receiving an INQUIRY message, it does not provide any information about the sender of the message. Therefore, an INQUIRY message received by the unit may also be transmitted by a slave unit, which is actually more likely, since there are usually more slave units than master units.
Waiting and hoping constitute no efficient method, but the Bluetooth specification allows an alternative way. The unit can itself send INQUIRY messages and hope to receive a response from the master unit of a piconet. However, the INQUIRY RESPONSE message, an FHS message, does not include any information on the fact whether the sender is a master or a slave of a piconet. Therefore, the unit has to take a chance and page and connect to a responding unit, hoping that the responding unit turns out to be the master of the piconet. If the unit is lucky, and actually manages to connect to the master unit of an existing piconet, a new piconet is formed having the inquiring and paging unit as the master unit and the paged master unit of the already existing piconet as a slave unit.
To join the old piconet the newly arrived unit has to request a master-slave switch. This master-slave switch will make the master unit of the old piconet, which is also a slave unit of the new piconet, a master also in the new piconet. Then, the two piconets will merge into one piconet making the new unit a slave unit in the merged piconet. Hence, joining an existing piconet as a slave unit requires first of all luck, and possibly also a master-slave switch.